from queue import Queue
class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        distance  = [float('inf') for _ in range(n+1)]
        distance[k] = 0
        distance[0] = 0
        q = Queue()
        q.put(k)
        maxtime = 0
        while not q.empty():
            que = q.get()
            for time in times:
                if time[0] == que and distance[time[1]] >=  time[2] + distance[que]:
                    distance[time[1]] = time[2] + distance[que]
                    q.put(time[1])
        if max(distance) == float('inf'):
            return -1
        else:
            return max(distance)
        

if __name__ == '__main__':
    s = Solution()
    print(s.networkDelayTime([[1,2,1],[2,3,2],[1,3,4]],3,1))